package leetcode.alg.demo;

/**
 * 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
 *
 * 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
 *
 * 示例 1：
 * 输入：n = 12
 * 输出：5
 *
 * 示例 2：
 * 输入：n = 13
 * 输出：6
 *
 * 限制：
 *
 * 1 <= n < 2^31
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class One_exists_number {

    public static void main(String[] args){
        System.out.println(countDigitOne(3234));
    }

    public static int countDigitOne(int n) {
        return f(n);
    }

    /**
     * (1). 例子如n=1234，high=1, pow=1000, last=234
     * 可以将数字范围分成两部分1~999和1000~1234
     *
     * 1~999这个范围1的个数是f(pow-1)
     * 1000~1234这个范围1的个数需要分为两部分：
     *   千分位是1的个数：千分位为1的个数刚好就是234+1(last+1)，注意，这儿只看千分位，不看其他位
     *   其他位是1的个数：即是234中出现1的个数，为f(last)
     * 所以全部加起来是f(pow-1) + last + 1 + f(last);
     *
     * (2). 例子如3234，high=3, pow=1000, last=234
     * 可以将数字范围分成两部分1~999，1000~1999，2000~2999和3000~3234
     *
     * 1~999这个范围1的个数是f(pow-1)
     * 1000~1999这个范围1的个数需要分为两部分：
     *   千分位是1的个数：千分位为1的个数刚好就是pow，注意，这儿只看千分位，不看其他位
     *   其他位是1的个数：即是999中出现1的个数，为f(pow-1)
     * 2000~2999这个范围1的个数是f(pow-1)
     * 3000~3234这个范围1的个数是f(last)
     * 所以全部加起来是pow + high*f(pow-1) + f(last);
     *
     * 作者：xujunyi
     * 链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/javadi-gui-by-xujunyi/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param n
     * @return
     */
    private static int f(int n){
        if(n <= 0){
            return 0;
        }
        String s = String.valueOf(n);
        int high = s.charAt(0) - '0';
        int pow = (int) Math.pow(10, s.length() - 1);
        int last = n - high * pow;
        if(high == 1){
            return f(pow - 1) + last + 1 + f(last);
        }else{
            return pow + high * f(pow - 1) + f(last);
        }
    }
}